package leetcode.code1499;

import java.util.Deque;
import java.util.LinkedList;

import leetcode.IDebug;
import leetcode.helper.H;

/**
 * 单调队列，不是最大的y，而是增加数量大排在队头 </br>
 * 增加数量是？ 两个点y的差是增加数量，x差是减少数量，如果y差 > x差，说明增加的多，那么这个点可以弹出前一个点</br>
 * 单调队列 LinkedList实现型 </br>
 * 
 * 执行用时：24 ms, 在所有 Java 提交中击败了26.76%的用户
 * 
 * 内存消耗：87.1 MB, 在所有 Java 提交中击败了77.46%的用户
 * 
 * 通过测试用例：66 / 66
 */
public class Solution_Deque implements IDebug {

	public int findMaxValueOfEquation(int[][] points, int k) {
		int ans = Integer.MIN_VALUE;
		Deque<Integer> queue = new LinkedList<>();
		for (int i = 0; i < points.length; i++) {
			int[] p = points[i];
			int x = p[0], y = p[1];
			while (!queue.isEmpty() && x - points[queue.peek()][0] > k) {
				queue.poll();
			}
			if (!queue.isEmpty()) {
				ans = Math.max(ans, y + points[queue.peek()][1] + x - points[queue.peek()][0]);
			}
			while (!queue.isEmpty() && y - points[queue.peekLast()][1] > x - points[queue.peekLast()][0]) {
				queue.pollLast();
			}
			queue.add(i);
		}
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(26,
				this.findMaxValueOfEquation(H.str2array1("[[-19,-12],[-5,-18],[2,-2],[10,3],[11,-3],[13,17]]"), 13));
		H.compare(4, this.findMaxValueOfEquation(H.str2array1("[[1,3],[2,0],[5,10],[6,-10]]"), 1));
		H.compare(3, this.findMaxValueOfEquation(H.str2array1("[[0,0],[3,0],[9,2]]"), 3));
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution_Deque so = new Solution_Deque();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
